In recent years, the development of three-dimensional shape measurement technology has enabled us to obtain the highly accurate three-dimensional data (called “3D data” hereinafter) of an object with non-geometrical and complex free-formed shape, and various fields such as graphics generation and image recognition system have started to utilize 3D data obtained by measuring the shape of a human body. Further, various three-dimensional data processing systems such as a storage system in which a large amount of 3D data is stored and recalled as necessary, a search system that quickly searches for desired data, and a system that performs object recognition by collating data with a group of stored 3D data have been proposed and put to practical use. For instance, an object collating apparatus that collates the image data of a collation object with the 3D data of a reference object registered in a storage device in advance is described in Patent Document 1.
The shape of a complex three-dimensional object such as a human body that cannot be described by combining geometric shapes such as cubes and cylinders is normally represented by an assembly of small planes of triangles and quadrilaterals called polygons that finely divide the surface of the object and is described by data expressing coordinate values of the vertex of each polygon in three-dimensional space. Further, the color information (texture) of the object surface is expressed by a luminance value as the color of each polygon vertex. As a typical expression of 3D data, there is a method in which a secondary coordinate system (s,t) is defined on the surface of the object just as latitude and longitude are defined on the surface of the earth, locations obtained by quantizing the coordinates at an appropriate interval are defined as the polygon vertices, and the three-dimensional coordinates and the color (r,g,b, luminance value) are stored as data. For instance, as shown in FIG. 11, a line that connects the gravity center of the object and a vertex is extended, and an intersection Q between the extended line and the surface of a sphere surrounding the object is derived. Then its latitude and longitude (s,t) are calculated. These values (s,t) are quantized at an appropriate interval and the (x,y,z) coordinates and the color information (r,g,b) of corresponding polygon vertices are stored. According to this method, the three-dimensional shape of an object and the color information of its surface are thought to be an image with each pixel having six elements or factors (x,y,z,r,g,b). Since three-dimensional coordinates have a wider range of values than the luminance value, the amount of three-dimensional data will be several times as much as the data of a luminance image having a resolution of the same level. For instance, if a surface area of 30 cm×30 cm is quantized at an interval of 1 mm, the vertex data will be a resolution of 300×300=90,000 points. If (x,y,z) are each described by two-byte data and (r,g,b) are described by one-byte data, the data amount will still be more than 800 kilobytes.
As described, compared to image data, the amount of three-dimensional data tends to be large, therefore data compression is used in order to reduce its size. Generally speaking, there are two kinds of data compression methods: reversible compression method that can accurately restore the original data from compressed data, although the data compression ratio is relatively low, and irreversible compression method that can achieve a high ratio of data compression while the restoration accuracy is not so high. Various kinds of the both methods are proposed or put into practice in order to reduce the amount of 3D data using polygons or a surface representation. For instance, a technology described in Patent Document 2 is a reversible compression technology. In this technology, a plurality of neighboring vertices are grouped and a reference point for each group is defined. The data amount is reduced by describing the groups using a data type having a small number of bits, taking advantage of the fact that the differentials from the reference points are small. Further, as an irreversible compression method, a method that deletes vertices in the order of the distance to an average polygon among neighboring polygons (from closest to farthest) until a specified thinning-out rate is achieved is proposed as described in Non-Patent Document 1.
Meanwhile, data compression techniques with the benefits of the both methods: high data compression ratio, which is the benefit of the irreversible compression method, and high accuracy, which is the benefit of the reversible compression method, are described in Patent Documents 3 or 4. In this technology, data obtained by compressing the original data using the irreversible compression method are called primary compressed data, data obtained by compressing the difference between data restored from the primary compressed data and the original data using the reversible compression method are called secondary compressed data, and a pair (or set) of the primary compressed data and the secondary compressed data becomes compressed data of the original data. This compression method will be called “hybrid compression method” hereinafter.
As a conventional technology that applies such a hybrid compression method to data processing, there is a data processing system described in Patent Document 5. In this system, when a search is performed on the compressed data, it is performed on the primary compressed data, and the search results are presented to the user in the form of data decompressed from the primary compressed data and the secondary compressed data (refer to Paragraph 64 in the document).
[Patent Document 1]
Japanese Patent Kokai Publication No. JP-P2002-157595A
[Patent Document 2]
Japanese Patent Kokai Publication No. JP-P2002-008060A
[Patent Document 3]
Japanese Patent Kokai Publication No. JP-A-63-045684
[Patent Document 4]
Japanese Patent Kokai Publication No. JP-A-10-290460
[Patent Document 5]
Japanese Patent Kokai Publication No. JP-A-10-285407 [Non-Patent Document 1]
W. J. Schroeder et al., “Decimation of Triangle Meshes,” Computer Graphics, 26, 2, Jul. 1992, pp. 65-70.